package net.neocat.tcx.util;

import com.google.common.collect.Lists;
import net.neocat.tcx.file.GeoPosition;

import java.util.ArrayList;
import java.util.List;

public final class RamerDouglasPeuckerFilter {
    private RamerDouglasPeuckerFilter() {
    }

    //adapted from http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm
    //original copyright message follows

    // Copyright 2002, softSurfer (www.softsurfer.com)
    // This code may be freely used and modified for any purpose
    // providing that this copyright notice is included with it.
    // SoftSurfer makes no warranty for this code, and cannot be held
    // liable for any real or imagined damage resulting from its use.
    // Users of this code must verify correctness for their application.

    /**
     * This method will reduce a 2D complex polyline.
     *
     * @param tol      the tolerance of the reduction algorithm. Higher numbers will simplify the line more.
     * @param vertexes the array of Positions to be simplified
     * @return an array of GeoPosition representing the simplified polyline
     */
    public static List<GeoPosition> simplifyLine2D(double tol, List<GeoPosition> vertexes) {

        int vertexCount = vertexes.size();

        double tol2 = tol * tol;
        GeoPosition[] vt = new GeoPosition[vertexCount];
        int[] mk = new int[vertexCount];

        ArrayList<GeoPosition> result = Lists.newArrayListWithCapacity(vertexes.size());

        for (int b = 0; b < vertexCount; b++) {
            mk[b] = 0;
        }

        //STAGE 1 simple vertex reduction
        vt[0] = vertexes.get(0);

        int k = 1;
        int pv = 0;
        for (int i = 1; i < vertexCount; i++) {
            if (vertexes.get(i).distanceSquared2D(vertexes.get(pv)) < tol2) {
                continue;
            }
            vt[k++] = vertexes.get(i);
            pv = i;
        }

        if (pv < vertexCount - 1) {
            vt[k++] = vertexes.get(vertexCount - 1);
        }

        //STAGE 2 Douglas-Peucker polyline simplify
        //mark the first and last vertices
        mk[0] = mk[k - 1] = 1;
        simplifyDP2D(tol, vt, 0, k - 1, mk);

        //copy marked vertices to output
        for (int i = 0, m = 0; i < k; i++) {
            if (mk[i] == 1) {
                result.add(vt[i]);
            }
        }

        return result;

    }

    private static void simplifyDP2D(double tol, GeoPosition[] v, int j, int k, int[] mk) {
        if (k <= j + 1) {
            return;  //nothing to simplify
        }

        final double tol2 = tol * tol;
        //Seg S = new Seg(v[j], v[k]);

        final GeoPosition u = v[k].minus(v[j]);
        final double cu = u.dot(u);

        double maxd2 = 0;
        int maxi = j;
        for (int i = j + 1; i < k; i++) {
            final GeoPosition w = v[i].minus(v[j]);
            final double cw = w.dot(u);
            final double dv2;
            if (cw <= 0)
                dv2 = v[i].distanceSquared2D(v[j]);
            else if (cu <= cw)
                dv2 = v[i].distanceSquared2D(v[k]);
            else {
                final double b = cw / cu;
                final GeoPosition pb = v[j].minus(u.times(-b));
                dv2 = v[i].distanceSquared2D(pb);
            }

            if (dv2 <= maxd2)
                continue;
            maxi = i;
            maxd2 = dv2;
        }
        if (maxd2 > tol2) {
            mk[maxi] = 1;
            simplifyDP2D(tol, v, j, maxi, mk);
            simplifyDP2D(tol, v, maxi, k, mk);

        }
        return;
    }

}
